A network graph depicts interconnections between nodes.
The presence or absence of each interconnection indicates whether there exists some form of connection between each pair of nodes.
Below is a randomly created adjacency matrix. ‘1’ denotes an edge (i.e., connection), and ‘0’ denotes the absence of an edge
set.seed(52)
pilotAdj <- sapply(1:10, function(x) sample(c(0,1),10,replace=T))
diag(pilotAdj) <- 0 # No self-connections
print(pilotAdj) [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 0 0 0 1 0 1 0 0 1 0
[2,] 1 0 1 0 1 0 1 1 0 0
[3,] 0 0 0 0 1 1 0 1 1 0
[4,] 0 1 0 0 0 0 0 0 0 1
[5,] 1 0 1 0 0 0 0 1 1 0
[6,] 0 1 0 0 1 0 1 0 1 0
[7,] 0 1 1 0 1 0 0 1 0 0
[8,] 1 1 1 1 0 1 0 0 0 0
[9,] 0 1 0 1 1 1 1 0 0 1
[10,] 1 1 0 0 1 1 0 0 1 0
This may seem abstract so let’s add some labels to the nodes to make it more meaningful:
people <- c("Luke","Anne","Zee","Bob","Tim","Jazmin","Juan","Kalani","Liz","Brent")
colnames(pilotAdj) <- people
rownames(pilotAdj) <- people
pilotAdj Luke Anne Zee Bob Tim Jazmin Juan Kalani Liz Brent
Luke 0 0 0 1 0 1 0 0 1 0
Anne 1 0 1 0 1 0 1 1 0 0
Zee 0 0 0 0 1 1 0 1 1 0
Bob 0 1 0 0 0 0 0 0 0 1
Tim 1 0 1 0 0 0 0 1 1 0
Jazmin 0 1 0 0 1 0 1 0 1 0
Juan 0 1 1 0 1 0 0 1 0 0
Kalani 1 1 1 1 0 1 0 0 0 0
Liz 0 1 0 1 1 1 1 0 0 1
Brent 1 1 0 0 1 1 0 0 1 0
In the adjacency matrix representation, a graph is represented in the form of a two-dimensional array. The size of the array is V x V, where V is the set of vertices. The following image represents the adjacency matrix representation:
An Adjacency list is an array consisting of the address of all the linked lists. The first node of the linked list represents the vertex and the remaining lists connected to this node represents the vertices to which this node is connected. This representation can also be used to represent a weighted graph. The linked list can slightly be changed to even store the weight of the edge.
IGRAPH 397f698 DN-- 10 42 --
+ attr: name (v/c)
+ edges from 397f698 (vertex names):
[1] Luke ->Bob Luke ->Jazmin Luke ->Liz Anne ->Luke Anne ->Zee
[6] Anne ->Tim Anne ->Juan Anne ->Kalani Zee ->Tim Zee ->Jazmin
[11] Zee ->Kalani Zee ->Liz Bob ->Anne Bob ->Brent Tim ->Luke
[16] Tim ->Zee Tim ->Kalani Tim ->Liz Jazmin->Anne Jazmin->Tim
[21] Jazmin->Juan Jazmin->Liz Juan ->Anne Juan ->Zee Juan ->Tim
[26] Juan ->Kalani Kalani->Luke Kalani->Anne Kalani->Zee Kalani->Bob
[31] Kalani->Jazmin Liz ->Anne Liz ->Bob Liz ->Tim Liz ->Jazmin
[36] Liz ->Juan Liz ->Brent Brent ->Luke Brent ->Anne Brent ->Tim
+ ... omitted several edges
An edge list is a list or array of all the edges in a graph. Edge lists are one of the easier representations of a graph. In this implementation, the underlying data structure for keeping track of all the nodes and edges is a single list of pairs. Each pair represents a single edge and is comprised of the two unique IDs of the nodes involved. Each line/edge in the graph gets an entry in the edge list, and that single data structure then encodes all nodes and relationships.
[,1] [,2]
[1,] "Luke" "Bob"
[2,] "Luke" "Jazmin"
[3,] "Luke" "Liz"
[4,] "Anne" "Luke"
[5,] "Anne" "Zee"
[6,] "Anne" "Tim"
[7,] "Anne" "Juan"
[8,] "Anne" "Kalani"
[9,] "Zee" "Tim"
[10,] "Zee" "Jazmin"
[11,] "Zee" "Kalani"
[12,] "Zee" "Liz"
[13,] "Bob" "Anne"
[14,] "Bob" "Brent"
[15,] "Tim" "Luke"
[16,] "Tim" "Zee"
[17,] "Tim" "Kalani"
[18,] "Tim" "Liz"
[19,] "Jazmin" "Anne"
[20,] "Jazmin" "Tim"
[21,] "Jazmin" "Juan"
[22,] "Jazmin" "Liz"
[23,] "Juan" "Anne"
[24,] "Juan" "Zee"
[25,] "Juan" "Tim"
[26,] "Juan" "Kalani"
[27,] "Kalani" "Luke"
[28,] "Kalani" "Anne"
[29,] "Kalani" "Zee"
[30,] "Kalani" "Bob"
[31,] "Kalani" "Jazmin"
[32,] "Liz" "Anne"
[33,] "Liz" "Bob"
[34,] "Liz" "Tim"
[35,] "Liz" "Jazmin"
[36,] "Liz" "Juan"
[37,] "Liz" "Brent"
[38,] "Brent" "Luke"
[39,] "Brent" "Anne"
[40,] "Brent" "Tim"
[41,] "Brent" "Jazmin"
[42,] "Brent" "Liz"
In the adjacency list representation, a graph is represented as an array of linked list. The index of the array represents a vertex and each element in its linked list represents the vertices that form an edge with the vertex. The following image represents the adjacency list representation:
$Luke
+ 7/10 vertices, named, from 397f698:
[1] Anne Bob Tim Jazmin Kalani Liz Brent
$Anne
+ 11/10 vertices, named, from 397f698:
[1] Luke Zee Bob Tim Jazmin Juan Juan Kalani Kalani Liz
[11] Brent
$Zee
+ 8/10 vertices, named, from 397f698:
[1] Anne Tim Tim Jazmin Juan Kalani Kalani Liz
$Bob
+ 5/10 vertices, named, from 397f698:
[1] Luke Anne Kalani Liz Brent
$Tim
+ 10/10 vertices, named, from 397f698:
[1] Luke Anne Zee Zee Jazmin Juan Kalani Liz Liz Brent
$Jazmin
+ 9/10 vertices, named, from 397f698:
[1] Luke Anne Zee Tim Juan Kalani Liz Liz Brent
$Juan
+ 7/10 vertices, named, from 397f698:
[1] Anne Anne Zee Tim Jazmin Kalani Liz
$Kalani
+ 9/10 vertices, named, from 397f698:
[1] Luke Anne Anne Zee Zee Bob Tim Jazmin Juan
$Liz
+ 11/10 vertices, named, from 397f698:
[1] Luke Anne Zee Bob Tim Tim Jazmin Jazmin Juan Brent
[11] Brent
$Brent
+ 7/10 vertices, named, from 397f698:
[1] Luke Anne Bob Tim Jazmin Liz Liz
Notably, you might see that an adjacency matrix is a “sparse matrix” and is distinct from the base R class of “matrix”. To convert it, you will need to go a step further.
10 x 10 sparse Matrix of class "dgCMatrix"
Luke . . . 1 . 1 . . 1 .
Anne 1 . 1 . 1 . 1 1 . .
Zee . . . . 1 1 . 1 1 .
Bob . 1 . . . . . . . 1
Tim 1 . 1 . . . . 1 1 .
Jazmin . 1 . . 1 . 1 . 1 .
Juan . 1 1 . 1 . . 1 . .
Kalani 1 1 1 1 . 1 . . . .
Liz . 1 . 1 1 1 1 . . 1
Brent 1 1 . . 1 1 . . 1 .
Luke Anne Zee Bob Tim Jazmin Juan Kalani Liz Brent
Luke 0 0 0 1 0 1 0 0 1 0
Anne 1 0 1 0 1 0 1 1 0 0
Zee 0 0 0 0 1 1 0 1 1 0
Bob 0 1 0 0 0 0 0 0 0 1
Tim 1 0 1 0 0 0 0 1 1 0
Jazmin 0 1 0 0 1 0 1 0 1 0
Juan 0 1 1 0 1 0 0 1 0 0
Kalani 1 1 1 1 0 1 0 0 0 0
Liz 0 1 0 1 1 1 1 0 0 1
Brent 1 1 0 0 1 1 0 0 1 0
+ 42/42 edges from 397f698 (vertex names):
[1] Luke ->Bob Luke ->Jazmin Luke ->Liz Anne ->Luke Anne ->Zee
[6] Anne ->Tim Anne ->Juan Anne ->Kalani Zee ->Tim Zee ->Jazmin
[11] Zee ->Kalani Zee ->Liz Bob ->Anne Bob ->Brent Tim ->Luke
[16] Tim ->Zee Tim ->Kalani Tim ->Liz Jazmin->Anne Jazmin->Tim
[21] Jazmin->Juan Jazmin->Liz Juan ->Anne Juan ->Zee Juan ->Tim
[26] Juan ->Kalani Kalani->Luke Kalani->Anne Kalani->Zee Kalani->Bob
[31] Kalani->Jazmin Liz ->Anne Liz ->Bob Liz ->Tim Liz ->Jazmin
[36] Liz ->Juan Liz ->Brent Brent ->Luke Brent ->Anne Brent ->Tim
[41] Brent ->Jazmin Brent ->Liz
Directed Graph: Directed graphs are a class of graphs that don’t presume symmetry or reciprocity in the edges established between vertices. In a directed graph, if and
are two vertices connected by an edge
, this doesn’t necessarily mean that an edge connecting
also exists
Undirected Graph: Symmetric; Undirected graphs are more specific. For them, there’s an extra assumption regarding the reciprocity in the relationship between pairs of vertices connected by an edge. If an edge exists between two vertices
and
, the edge
also exists
Examples of directed graphs include parents and their offspring; Twitter
Examples of undirected graphs include pedestrian pathways, where movement between any two intersections of paths is possible in both directions; railways; Facebook; correlation matrices
Our prior adjacency matrix we generated is a directed graph.
10 x 10 sparse Matrix of class "dgCMatrix"
Luke . . . 1 . 1 . . 1 .
Anne 1 . 1 . 1 . 1 1 . .
Zee . . . . 1 1 . 1 1 .
Bob . 1 . . . . . . . 1
Tim 1 . 1 . . . . 1 1 .
Jazmin . 1 . . 1 . 1 . 1 .
Juan . 1 1 . 1 . . 1 . .
Kalani 1 1 1 1 . 1 . . . .
Liz . 1 . 1 1 1 1 . . 1
Brent 1 1 . . 1 1 . . 1 .
set.seed(48)
pilotAdjUn <- sapply(1:10, function(x) sample(c(0,1),10,replace=T))
pilotAdjUn[lower.tri(pilotAdjUn)] = t(pilotAdjUn)[lower.tri(pilotAdjUn)]
diag(pilotAdjUn) <- 0
pilotAdjUn [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,] 0 0 0 1 1 0 1 1 0 0
[2,] 0 0 1 1 0 0 1 0 0 0
[3,] 0 1 0 1 1 0 1 1 0 1
[4,] 1 1 1 0 0 0 1 1 1 0
[5,] 1 0 1 0 0 0 1 0 0 0
[6,] 0 0 0 0 0 0 1 0 0 0
[7,] 1 1 1 1 1 1 0 1 1 1
[8,] 1 0 1 1 0 0 1 0 1 0
[9,] 0 0 0 1 0 0 1 1 0 0
[10,] 0 0 1 0 0 0 1 0 0 0
pilotGraphUn <- graph_from_adjacency_matrix(pilotAdjUn, mode="undirected")
is.directed(pilotGraphUn)[1] FALSE
If we care only if two nodes are connected or not, we call such a graph unweighted. For the nodes with an edge between them, we say they are adjacent or neighbors of one another.
In many applications, the edges have numerical properties that we need to exploit in our algorithms to solve the problem at hand. For example, we must consider road lengths and traffic density while looking for the shortest path between two cities. So, we associate each edge with a real value
that we call its weight. We call such graphs weighted.
10 x 10 sparse Matrix of class "dgCMatrix"
Luke . . . -1.0800526 . 1.8262535
Anne -0.3033929 . 0.04874371 . -0.89683593 .
Zee . . . . -0.41426188 -1.3985065
Bob . -0.5514779390 . . . .
Tim -0.5062032 . -0.43876859 . . .
Jazmin . 0.0003886532 . . -0.35249792 .
Juan . -0.9084064952 -0.16432731 . -0.63373542 .
Kalani -0.6270644 0.7297462996 1.98264432 0.3165565 . -1.1625891
Liz . 1.3719967855 . -1.0852256 -0.07191939 -0.8335206
Brent 1.1605596 -0.2095287169 . . -0.70486068 0.1487730
Luke . . -0.36631444 .
Anne 1.2561356 0.9715358 . .
Zee . 0.9341368 -0.07047117 .
Bob . . . 0.6058275
Tim . 0.2990072 -1.26668638 .
Jazmin -0.9197363 . 0.88531943 .
Juan . -0.7463273 . .
Kalani . . . .
Liz -0.5573352 . . 1.5574155
Brent . . 0.12432662 .
$name
[1] "Luke" "Anne" "Zee" "Bob" "Tim" "Jazmin" "Juan" "Kalani"
[9] "Liz" "Brent"
$party
[1] "Dem" "Dem" "Rep" "Dem" "Rep" "Dem" "Rep" "Dem" "Dem" "Rep"
[1] "Dem" "Dem" "Rep" "Dem" "Rep" "Dem" "Rep" "Dem" "Dem" "Rep"
[1] -0.32649141 0.41635369 0.01981900 -0.65516483 0.61464925 0.91149901
[7] -0.39453189 -0.22837836 -0.68597361 2.33719057 0.43163957 0.58103320
[13] 1.88668458 -0.70263564 2.13005539 -0.18521698 1.30723730 -0.10481191
[19] -1.12511912 0.90967468 2.67016095 0.24883337 -1.94102816 -0.98296103
[25] -1.06348692 0.87797022 -0.27141087 0.47532044 0.86695653 -0.06351474
[31] -1.29585987 -0.56441804 -0.09103845 -0.69537905 -1.02493045 2.06080413
[37] -0.20601530 0.10293105 0.44809381 1.08050718 1.00996288 0.89496548
$friendship
[1] -0.32649141 0.41635369 0.01981900 -0.65516483 0.61464925 0.91149901
[7] -0.39453189 -0.22837836 -0.68597361 2.33719057 0.43163957 0.58103320
[13] 1.88668458 -0.70263564 2.13005539 -0.18521698 1.30723730 -0.10481191
[19] -1.12511912 0.90967468 2.67016095 0.24883337 -1.94102816 -0.98296103
[25] -1.06348692 0.87797022 -0.27141087 0.47532044 0.86695653 -0.06351474
[31] -1.29585987 -0.56441804 -0.09103845 -0.69537905 -1.02493045 2.06080413
[37] -0.20601530 0.10293105 0.44809381 1.08050718 1.00996288 0.89496548
[1] -0.32649141 0.41635369 0.01981900 -0.65516483 0.61464925 0.91149901
[7] -0.39453189 -0.22837836 -0.68597361 2.33719057 0.43163957 0.58103320
[13] 1.88668458 -0.70263564 2.13005539 -0.18521698 1.30723730 -0.10481191
[19] -1.12511912 0.90967468 2.67016095 0.24883337 -1.94102816 -0.98296103
[25] -1.06348692 0.87797022 -0.27141087 0.47532044 0.86695653 -0.06351474
[31] -1.29585987 -0.56441804 -0.09103845 -0.69537905 -1.02493045 2.06080413
[37] -0.20601530 0.10293105 0.44809381 1.08050718 1.00996288 0.89496548
IGRAPH a6f554a DN-- 6 15 --
+ attr: name (v/c), party (v/c), friendship (e/n)
+ edges from a6f554a (vertex names):
[1] Luke ->Bob Luke ->Jazmin Luke ->Liz Anne ->Luke Anne ->Kalani
[6] Bob ->Anne Jazmin->Anne Jazmin->Liz Kalani->Luke Kalani->Anne
[11] Kalani->Bob Kalani->Jazmin Liz ->Anne Liz ->Bob Liz ->Jazmin
+ 11/42 edges from 397f698 (vertex names):
tail head tid hid friendship
4 Anne Luke 2 1 -0.6551648
5 Anne Zee 2 3 0.6146492
6 Anne Tim 2 5 0.9114990
7 Anne Juan 2 7 -0.3945319
8 Anne Kalani 2 8 -0.2283784
13 Bob Anne 4 2 1.8866846
19 Jazmin Anne 6 2 -1.1251191
23 Juan Anne 7 2 -1.9410282
28 Kalani Anne 8 2 0.4753204
32 Liz Anne 9 2 -0.5644180
39 Brent Anne 10 2 0.4480938
+ 22/42 edges from 397f698 (vertex names):
tail head tid hid friendship
2 Luke Jazmin 1 6 0.4163537
3 Luke Liz 1 9 0.0198190
5 Anne Zee 2 3 0.6146492
6 Anne Tim 2 5 0.9114990
10 Zee Jazmin 3 6 2.3371906
11 Zee Kalani 3 8 0.4316396
12 Zee Liz 3 9 0.5810332
13 Bob Anne 4 2 1.8866846
15 Tim Luke 5 1 2.1300554
17 Tim Kalani 5 8 1.3072373
20 Jazmin Tim 6 5 0.9096747
21 Jazmin Juan 6 7 2.6701609
22 Jazmin Liz 6 9 0.2488334
26 Juan Kalani 7 8 0.8779702
28 Kalani Anne 8 2 0.4753204
29 Kalani Zee 8 3 0.8669565
36 Liz Juan 9 7 2.0608041
38 Brent Luke 10 1 0.1029310
39 Brent Anne 10 2 0.4480938
40 Brent Tim 10 5 1.0805072
41 Brent Jazmin 10 6 1.0099629
42 Brent Liz 10 9 0.8949655
Any edges to or from a given vertex... Here, for “Anne”
We can subset any nodes that are neighboring a node.
We can use intersection to discover this.
[[1]]
+ 6/10 vertices, named, from 397f698:
[1] Bob Luke Anne Kalani Liz Brent
ego(pilotGraph, order=1, mindist = 1, nodes = "Bob") # 1 step away, not including Bob which is identical to neighbors() output[[1]]
+ 5/10 vertices, named, from 397f698:
[1] Luke Anne Kalani Liz Brent
[[1]]
+ 10/10 vertices, named, from 397f698:
[1] Bob Luke Anne Kalani Liz Brent Tim Jazmin Zee Juan
The distance between these two nodes reflect the diameter of the network?
As you can see, the diameter returns the same distance as is observed in farthest vertices.
You can extract a table of all distances among all nodes as well.
Luke Anne Zee Bob Tim Jazmin Juan Kalani Liz Brent
Luke 0 1 2 1 1 1 2 1 1 1
Anne 1 0 1 1 1 1 1 1 1 1
Zee 2 1 0 2 1 1 1 1 1 2
Bob 1 1 2 0 2 2 2 1 1 1
Tim 1 1 1 2 0 1 1 1 1 1
Jazmin 1 1 1 2 1 0 1 1 1 1
Juan 2 1 1 2 1 1 0 1 1 2
Kalani 1 1 1 1 1 1 1 0 2 2
Liz 1 1 1 1 1 1 1 2 0 1
Brent 1 1 2 1 1 1 2 2 1 0
The vertex similarity coefficient of a pair of vertices is a measure of how similar are the immediate networks of those two vertices. Imagine we have two vertices V1 and V2 in an unweighted graph G. There are three common ways to calculate the vertex similarity of V1 and V2.
The Jaccard similarity coefficient is the number of vertices who are neighbors of both V1 and V2 divided by the number of vertices who are neighbors of at least one of V1 and V2.
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 1.000 0.6 0.6250000 0.500 0.5000000 0.5000000 0.6250000 0.4000000
[2,] 0.600 1.0 0.5000000 0.400 0.7000000 0.7000000 0.5000000 0.6000000
[3,] 0.625 0.5 1.0000000 0.375 0.5555556 0.5555556 0.7142857 0.4444444
[4,] 0.500 0.4 0.3750000 1.000 0.6250000 0.6250000 0.3750000 0.2000000
[5,] 0.500 0.7 0.5555556 0.625 1.0000000 0.7777778 0.5555556 0.5000000
[6,] 0.500 0.7 0.5555556 0.625 0.7777778 1.0000000 0.5555556 0.5000000
[7,] 0.625 0.5 0.7142857 0.375 0.5555556 0.5555556 1.0000000 0.4444444
[8,] 0.400 0.6 0.4444444 0.200 0.5000000 0.5000000 0.4444444 1.0000000
[9,] 0.500 0.7 0.4000000 0.300 0.6000000 0.6000000 0.4000000 0.8750000
[10,] 0.625 0.5 0.5000000 0.375 0.4000000 0.4000000 0.5000000 0.6250000
[,9] [,10]
[1,] 0.5000000 0.6250000
[2,] 0.7000000 0.5000000
[3,] 0.4000000 0.5000000
[4,] 0.3000000 0.3750000
[5,] 0.6000000 0.4000000
[6,] 0.6000000 0.4000000
[7,] 0.4000000 0.5000000
[8,] 0.8750000 0.6250000
[9,] 1.0000000 0.5555556
[10,] 0.5555556 1.0000000
The dice similarity coefficient is twice the number of vertices who are neighbors of both v1�1 and v2�2 divided by the sum of the degree centralities of v1�1 and v2�2. Thus, common neighbors are double counted in this method.
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 1.0000000 0.7500000 0.7692308 0.6666667 0.6666667 0.6666667 0.7692308
[2,] 0.7500000 1.0000000 0.6666667 0.5714286 0.8235294 0.8235294 0.6666667
[3,] 0.7692308 0.6666667 1.0000000 0.5454545 0.7142857 0.7142857 0.8333333
[4,] 0.6666667 0.5714286 0.5454545 1.0000000 0.7692308 0.7692308 0.5454545
[5,] 0.6666667 0.8235294 0.7142857 0.7692308 1.0000000 0.8750000 0.7142857
[6,] 0.6666667 0.8235294 0.7142857 0.7692308 0.8750000 1.0000000 0.7142857
[7,] 0.7692308 0.6666667 0.8333333 0.5454545 0.7142857 0.7142857 1.0000000
[8,] 0.5714286 0.7500000 0.6153846 0.3333333 0.6666667 0.6666667 0.6153846
[9,] 0.6666667 0.8235294 0.5714286 0.4615385 0.7500000 0.7500000 0.5714286
[10,] 0.7692308 0.6666667 0.6666667 0.5454545 0.5714286 0.5714286 0.6666667
[,8] [,9] [,10]
[1,] 0.5714286 0.6666667 0.7692308
[2,] 0.7500000 0.8235294 0.6666667
[3,] 0.6153846 0.5714286 0.6666667
[4,] 0.3333333 0.4615385 0.5454545
[5,] 0.6666667 0.7500000 0.5714286
[6,] 0.6666667 0.7500000 0.5714286
[7,] 0.6153846 0.5714286 0.6666667
[8,] 1.0000000 0.9333333 0.7692308
[9,] 0.9333333 1.0000000 0.7142857
[10,] 0.7692308 0.7142857 1.0000000
The inverse log-weighted similarity coefficient is the sum of the inverse logs of the degrees of the common neighbors of V1 and V2. This definition asserts that common neighbors that have high degree in the network are ‘less valuable’ in detecting similarity because there is a higher likelihood that they would be a common neighbor simply by chance.
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 0.000000 3.351919 3.068013 1.803083 2.675235 2.6544096 2.5956309 2.344814
[2,] 3.351919 1.938036 4.589016 2.355068 5.216814 4.7150902 2.6975841 4.014241
[3,] 3.068013 4.589016 1.778828 1.744304 3.130354 3.5438237 3.4850450 2.671672
[4,] 1.803083 2.355068 1.744304 0.000000 2.734013 2.7340135 1.7062168 1.347963
[5,] 2.675235 5.216814 3.130354 2.734013 1.795861 5.0437733 3.5401655 4.240574
[6,] 2.654410 4.715090 3.543824 2.734013 5.043773 0.8340648 3.0384420 3.257953
[7,] 2.595631 2.697584 3.485045 1.706217 3.540165 3.0384420 0.8340648 3.519340
[8,] 2.344814 4.014241 2.671672 1.347963 4.240574 3.2579526 3.5193404 1.795861
[9,] 3.844992 5.450553 3.578348 1.958727 4.344662 3.8221131 3.0937913 5.223821
[10,] 2.761846 2.858712 2.574806 1.764996 3.054180 3.0333548 2.5575437 2.858712
[,9] [,10]
[1,] 3.844992 2.7618462
[2,] 5.450553 2.8587122
[3,] 3.578348 2.5748058
[4,] 1.958727 1.7649955
[5,] 4.344662 3.0541799
[6,] 3.822113 3.0333548
[7,] 3.093791 2.5575437
[8,] 5.223821 2.8587122
[9,] 2.806625 3.3310939
[10,] 3.331094 0.8340648
Degree centrality assigns an importance score based simply on the number of links held by each node.
Simple, straightforward measure of overall connections. Can distinguish between out and in-degree centrality in directed graph.
The closeness centrality of a vertex v in a connected graph is the inverse of the sum of the distances from v to all other vertices. Closeness centrality is a measure of how efficiently the entire graph can be traversed from a given vertex.
The betweenness centrality of a vertex V is calculated by taking each pair of other vertices X and Y, calculating the number of shortest paths between X and Y that go through V, dividing by the total number of shortest paths between X and Y, then summing over all such pairs of vertices in the graph. Betweenness centrality is a measure of how important a given vertex is in connecting other pairs of vertices in the graph… how frequently the vertex lies on shortest paths between any two vertices in the network.
The Eigenvector centrality or relative centrality or prestige of a vertex is a measure of how connected the vertex is to other influential vertices. EigenCentrality measures a node’s influence based on the number of links it has to other nodes in the network. EigenCentrality then goes a step further by also taking into account how well connected a node is, and how many links their connections have, and so on through the network.
PageRank is a variant of EigenCentrality, also assigning nodes a score based on their connections, and their connections’ connections. The difference is that PageRank also takes link direction and weight into account – so links can only pass influence in one direction, and pass different amounts of influence.
The proportion of all potential edges between vertices that actually exist in the network graph. It is an indicator of how well connected the vertices of the graph are.
The mean of the lengths of the shortest paths between all pairs of vertices in the network.
Probability that the adjacent verticles of a given vertex are connected (e.g., triangles)
Metric calculates the proportion of closed triangles that a vertex is part of, given the number of triangles it could be a part of
All vertices connected to each other.
[[1]]
+ 4/10 vertices, named, from 397f698:
[1] Bob Luke Anne Kalani
[[2]]
+ 5/10 vertices, named, from 397f698:
[1] Bob Luke Anne Brent Liz
[[3]]
+ 5/10 vertices, named, from 397f698:
[1] Luke Anne Jazmin Tim Kalani
[[4]]
+ 6/10 vertices, named, from 397f698:
[1] Luke Anne Jazmin Tim Brent Liz
[[5]]
+ 6/10 vertices, named, from 397f698:
[1] Juan Anne Jazmin Tim Zee Kalani
[[6]]
+ 6/10 vertices, named, from 397f698:
[1] Juan Anne Jazmin Tim Zee Liz
Do similar nodes connect to each other?
You can calculate assortativity based on categories (nominal), numeric values, or degree centrality
What is the probability of an edge going both ways?
Where are connections between nodes more dense?
Only work on undirected graphs
IGRAPH clustering fast greedy, groups: 5, mod: 0.56
+ groups:
$`1`
[1] 2 8 11 15 18 19 21 25 29 31 34 35 39 41 43 46 57 58 79
$`2`
[1] 24 32 37 38 48 50 52 54 55 64 70
$`3`
[1] 1 3 4 9 17 36 44 45 53 59 60 61 62 73 74 75 78 81
$`4`
+ ... omitted several groups/vertices
Dividing into smaller pieces until identifies bridges between communities
IGRAPH clustering edge betweenness, groups: 14, mod: 0.12
+ groups:
$`1`
[1] 1
$`2`
[1] 2 3 4 5 7 8 9 10 12 13 16 17 18 19 21 23 25 27 28 29 31 33 35 37
[25] 38 40 41 42 43 46 48 49 50 51 52 53 54 58 59 60 61 62 65 68 69 70 71 72
[49] 73 74 75 76 77 78 79 81
$`3`
[1] 6 22 30 66
+ ... omitted several groups/vertices
# Plot the graph object pilotGraph in a circle layout
plot(pilotGraph, vertex.label.color = "black", layout = layout_in_circle(pilotGraph))# Plot the graph object pilotGraph in a Fruchterman-Reingold layout
plot(pilotGraph, vertex.label.color = "black", layout = layout_with_fr(pilotGraph))# Plot the graph object pilotGraph in a Tree layout
m <- layout_as_tree(pilotGraph)
plot(pilotGraph, vertex.label.color = "black", layout = m)# Plot the graph object pilotGraph using igraph's chosen layout
m1 <- layout_nicely(pilotGraph)
plot(pilotGraph, vertex.label.color = "black", layout = m1)You can conditionally assign colors based on some attribute and plot based off that attribute. igraph vertices have an attribute for color.
# Plot the two largest cliques side-by-side
par(mfrow=c(1,2)) # To plot two plots side-by-side
plot(gs1,
vertex.label.color = "black",
vertex.label.cex = 0.9,
vertex.size = 0,
edge.color = 'gray28',
main = "Largest Clique 1",
layout = layout.circle(gs1)
)
plot(gs2,
vertex.label.color = "black",
vertex.label.cex = 0.9,
vertex.size = 0,
edge.color = 'gray28',
main = "Largest Clique 2",
layout = layout.circle(gs2)
)Depiction of assortativity
# select colors
colors = brewer.pal(4, "Dark2")
# assign colors to groups
V(UKfaculty)$color = sapply(V(UKfaculty)$Group, function(x) colors[x])
plot(UKfaculty, layout = layout_nicely(UKfaculty, dim = 2),
vertex.color = V(UKfaculty)$color, vertex.frame.color = NA,
vertex.label = NA, vertex.shape = 'square',
vertex.size = 3.5, edge.arrow.size = 0.3, edge.curved = TRUE,
edge.width = E(UKfaculty)$weight ^ 0.8,
edge.color = rgb(0, 0, 0, alpha = 0.1))
title("UK Faculty Friendship Network (Directed)", cex.main = 1)